package com.aqie.easy.binarySearch;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 167 两数之和 有序数组
 */
public class TwoSum {
    /**
     * 1， 8ms 二分查找
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum(int[] numbers, int target) {
        int N = numbers.length;
        int[] ans = new int[2];
        for (int i = 0; i < N; i++){

            int j = indexOf(numbers, target - numbers[i]);
            if (j == -1) continue;
            System.out.println(i + " " + j);
            if (j == i) {
               if (numbers[i + 1] == target - numbers[i]){
                   ans[0] = i + 1;
                   ans[1] = j + 1 + 1;
                   return ans;
               }else if (numbers[i - 1] == target - numbers[i]){
                   ans[0] = i + 1;
                   ans[1] = j + 1 - 1;
                   return ans;
               }
            }else{
                ans[0] = i + 1;
                ans[1] = j + 1;
                return ans;
            }
        }
        return ans;
    }

    private int indexOf(int[] a, int key) {
        int lo = 0;
        int hi = a.length - 1;
        // l = 0, h = 7 mid = 3
        while (lo <= hi) {
            // Key is in a[lo..hi] or not present.
            int mid = lo + (hi - lo) / 2;
            if (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else return mid;
        }
        return -1;
    }

    /**
     * 2, 双指针 1ms
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum2(int[] numbers, int target) {
        int[] ans = new int[2];
        int low = 0, high = numbers.length - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                ans[0] = low + 1;
                ans[1] = high + 1;
                return ans;
            }
            else if (sum < target)
                ++low;
            else
                --high;
        }
        return ans;

    }

    /**
     * 支持重复元素二分查找
     * @param A
     * @param x
     * @return
     */
    private List<Integer> binarySearch2(Integer[] A, Integer x) {
        List<Integer> result = new ArrayList<Integer>();
        int low = 0, high = A.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (A[mid].equals(x)) {
                if (mid > 0) {
                    //看前一个元素是否＝目标元素
                    if (A[mid - 1].equals(x)) {
                        for (int i = mid - 1; i >= 0; i--) {
                            if (A[i].equals(x)) {
                                result.add(i);
                            } else break;
                        }
                    }
                }
                result.add(x);
                if (mid < high) {
                    //看后一个元素是否＝目标元素
                    if (A[mid + 1].equals(x)) {
                        for (int i = mid + 1; i <= high; i++) {
                            if (A[i].equals(x)) {
                                result.add(i);
                            } else break;
                        }
                    }
                }
                return result;
            } else if (x < A[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return result;

    }

    /**
     * 泛型支持重复元素
     * @param A
     * @param x
     * @param comparator
     * @param <T>
     * @return
     */
    private <T> List<Integer> binarySearch4(List<T> A, T x, Comparator<? super T> comparator) {
        List<Integer> result = new ArrayList<Integer>();
        int low = 0, high = A.size() - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            int temp = comparator.compare(x, A.get(mid));
            if (temp == 0) {
                if (mid > 0) {
                    if (comparator.compare(x, A.get(mid - 1)) == 0) {
                        for (int i = mid - 1; i >= 0; i--) {
                            if (comparator.compare(A.get(i), x) == 0) {
                                result.add(i);
                            } else break;
                        }
                    }
                }
                result.add(mid);
                if (mid < high) {
                    if (comparator.compare(x, A.get(mid + 1)) == 0) {
                        for (int i = mid + 1; i <= high; i++) {
                            if (comparator.compare(x, A.get(i)) == 0) {
                                result.add(i);
                            } else break;
                        }
                    }
                }
                return result;

            } else if (temp < 0) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        /*int[] numbers = {2,7,11,15};
        int target = 9;*/

        /*int[] numbers = {1,2,3,4,4,9,56,90};
        int target = 8;*/

        int[] numbers = {1,2,3,3,4,4,56,90};
        int target = 8;
        System.out.println(Arrays.toString(new TwoSum().twoSum(numbers, target)));

        System.out.println((0 + 7) / 2);


    }

}
